This disclosure relates generally to data processing, and more particularly to techniques for drawing curved edges in graphs.
Graphs are used to represent information in many disciplines such as software applications, communication networks and web data analysis. Well-drawn graphs make it easy to visualize and comprehend the represented information. The term “Aesthetics of Graph” is used herein to refer to the how well a graph's nodes are laid out and its edges are drawn.
Edge drawing is an important part of graph aesthetics. An edge is considered aesthetically better if it is easy to follow (i.e. trace), but often nodes obstruct the straight line route for the edges. To keep the edges straight, it is not acceptable to shift the nodes and compromise on the graph compactness. So there is a need to draw curved edges rather than straight edges. Based on hand-made drawings, it is observed that the following principles lead to aesthetically better curved edges:                Draw smooth edges and avoid sharp edge bends        Minimize edge crossings and congestion.        Keep edges short and reduce the curvature as much as possible        
It is difficult to optimize all of above aesthetics goals simultaneously. In fact, it is computationally intractable to minimize edge crossings or to draw edges that make the graph symmetric. For an algorithm to be useful in interactive application, the necessary computation for edge drawing has to be done in real-time.
Edge drawing is one of the most fundamental problems in Graph Drawing and there have been many papers published in this field. Edge drawing algorithms can be categorized into two groups. In the first group, edges are drawn at the time of laying out nodes, such as using Force Directed techniques. These techniques work well for very small graphs, but fail to perform well for larger graphs. These algorithms use the location of already drawn edges to determine the location of nodes laid out later. This limitation rules out the possibility of using these algorithms in interactive environments, where a user can specify or change the node locations.
In a second group of algorithms, the edges are routed after all the nodes have been laid out. There are two basic edge types that are used in general, namely, polyline (straight line and orthogonal being its special cases) and curved. As discussed earlier, straight line drawings cannot always avoid intersection of edges with nodes. Orthogonal drawings are not very compact and become completely incomprehensible in large graphs. Polyline edges are not smooth, hence are not considered good aesthetically. The smooth curves, as they are drawn in handmade drawings, are considered to be visually most appealing.
A general approach for drawing a smooth curve is to compute a piecewise linear path unobstructed by nodes and then to smoothen it out using Bezier curves. This approach has been used in several conventional algorithms such as Dag, dot, and router, but still these algorithms have several limitations. These algorithms are very heavily biased towards computing the shortest possible curved route. This often results in a large number of bends and turns in the piecewise linear path, which is seen in the final smoothened spline. A large number of bends and turns, even with small curvature, disrupts the visual flow and makes it difficult to follow the nodes that these edges connect.
Most conventional algorithms do not try to minimize the intersection of edges by placing the curves suitably, and the algorithms (such as dot) that do minimize the edge intersections compromise on the curve length and result in very long and curvy edges. In addition, the computations take too much time.
Conventional algorithms try to maximize on one or two of the aesthetic principles while ignoring the others. This creates the need for techniques that can create smooth curved edges and also satisfy various aesthetics principles at the same time.